package com.sheng.leetcode.year2023.month05.day22;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/05/22
 * <p>
 * 1080. 根到叶路径上的不足节点<p>
 * <p>
 * 给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。<p>
 * 假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。<p>
 * 叶子节点，就是没有子节点的节点。<p>
 * <p>
 * 示例 1：<p>
 * 输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1<p>
 * 输出：[1,2,3,4,null,null,7,8,9,null,14]<p>
 * <p>
 * 示例 2：<p>
 * 输入：root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22<p>
 * 输出：[5,4,8,11,null,17,4,7,null,null,null,5]<p>
 * <p>
 * 示例 3：<p>
 * 输入：root = [1,2,-3,-5,null,4,null], limit = -1<p>
 * 输出：[1,null,-3,4]<p>
 * <p>
 * 提示：<p>
 * 树中节点数目在范围 [1, 5000] 内<p>
 * -10^5 <= Node.val <= 10^5<p>
 * -10^9 <= limit <= 10^9<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths">1080. 根到叶路径上的不足节点</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1080 {

    @Test
    public void test01() {
//        TreeNode left1 = new TreeNode(4);
//        left1.left = new TreeNode(8);
//        left1.right = new TreeNode(9);
//        TreeNode right1 = new TreeNode(-99);
//        right1.left = new TreeNode(-99);
//        right1.right = new TreeNode(-99);
//        TreeNode left = new TreeNode(2);
//        left.left = left1;
//        left.right = right1;
//        TreeNode left2 = new TreeNode(-99);
//        left2.left = new TreeNode(12);
//        left2.right = new TreeNode(13);
//        TreeNode right2 = new TreeNode(7);
//        right2.left = new TreeNode(-99);
//        right2.right = new TreeNode(14);
//        TreeNode right = new TreeNode(3);
//        right.left = left2;
//        right.right = right2;
//        TreeNode root = new TreeNode(1);
//        root.left = left;
//        root.right = right;
//        int limit = 1;

//        TreeNode left1 = new TreeNode(11);
//        left1.left = new TreeNode(7);
//        left1.right = new TreeNode(1);
//        TreeNode left = new TreeNode(4);
//        left.left = left1;
//        TreeNode right2 = new TreeNode(4);
//        right2.left = new TreeNode(5);
//        right2.right = new TreeNode(3);
//        TreeNode right = new TreeNode(8);
//        right.left = new TreeNode(17);
//        right.right = right2;
//        TreeNode root = new TreeNode(5);
//        root.left = left;
//        root.right = right;
//        int limit = 22;

//        TreeNode left = new TreeNode(2);
//        left.left = new TreeNode(-5);
//        TreeNode right = new TreeNode(-3);
//        right.left = new TreeNode(4);
//        TreeNode root = new TreeNode(1);
//        root.left = left;
//        root.right = right;
//        int limit = -1;

        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(10);
        int limit = 21;
        TreeNode treeNode = new Solution().sufficientSubset(root, limit);
        System.out.println(treeNode);
    }
}

class Solution {

    int limit;

    public TreeNode sufficientSubset(TreeNode root, int limit) {
        // 解读，从当前结点一直到所有的子节点，删除和小余 limit 的结点
        // 思路：遍历子节点，判断是否需要被删除，当前结点的所有结点都不满足时，代表当前结点也需要被删除（注
        this.limit = limit;
        boolean dfs = dfs(root, 0);
        return dfs ? null : root;
    }

    public boolean dfs(TreeNode root, int parent) {
        if (root.left == null && root.right == null) {
            return parent + root.val < limit;
        } else {
            boolean left = false, right = false;
            if (root.left != null) {
                left = dfs(root.left, parent + root.val);
                if (left) {
                    root.left = null;
                }
            } else {
                left = true;
            }
            if (root.right != null) {
                right = dfs(root.right, parent + root.val);
                if (right) {
                    root.right = null;
                }
            } else {
                right = true;
            }
            return left && right;
        }
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
